#include <stdio.h>
#include <stdlib.h>

#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P, tmp;
    int N;

    L = NULL;
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        L = Insert(L, X, L);
        if ( L==ERROR ) printf("Wrong Answer\n");
    }
    scanf("%d", &N);


    return 0;
}

/* 你的代码将被嵌在这里 */
/*
 * 代码分析思路：
 *
 * （1） 从main()函数里Insert函数的调用情况来看（ L = Insert(L, X, L);），待插入位置 P其实始终是链表L的头结点即L==P（L），因此：
 *      插入效果为链表逆序插入
 *      因此，假设新结点为new ,则逆序插入需要new.next=L;
 *  （2）如果P！=L，即P不赋值为L时，实现的是普通的中间插入，例如， L = Insert(L, X, NULL); 此时其实是中间插入的特殊情况（尾部插入）
 *      此时插入需要提前找对位置，找位置根据当前结点cur.data==P.data与否，查找结构有两种：
 *        2.1 没有找到，返回错误标志ERROR
 *        2.2 找到，执行插入动作
 *
 *
 *
 * */
List Insert( List L, ElementType X, Position P ){

    //无论链表是正序插入还是中间插入，只要插入，就需要开辟新结点，因此，可以放在最前面
    //创建新节点 开辟空间存放插入的元素
    Position new = malloc(sizeof (Position));
    new->Data = X;
    new->Next = NULL;

    // (1) 当P赋值为L时，实现逆序插入
    if(L == P){
        new->Next=L;
        return new;
    } else{  //（2）当P！=L时，实现普通的中间插入
        //链表不为空，执行插入之前就要先找到位置，因此先进行查找
        //2根据内容进行查找
        Position pre = L;

        while(pre!=NULL){
            if(pre->Next==P){//找到位置，执行插入
                Position cur = pre->Next;
                pre->Next = new;
                new->Next = cur->Next;
                return L;
            } else{
                //没有找到位置，则查找指针pre移动到后面
                pre = pre->Next;
            }
        }
        //while 循环结束没找到
        printf("Wrong Position for Insertion\n");
        return ERROR;
    }

}

